package com.lecode.LRU.lru2;

import java.util.HashMap;

/**
 * 最近最近未使用
 * LRU
 */
public class LRUCache {

    /**哈希表*/
    private HashMap<Integer, Node> map;

    /**双向链表：尾结点为最近使用   头结点为最近最久未使用*/
    private LinkNode cache;

    /**缓存最大容量*/
    private Integer cap;

    public LRUCache(Integer cap){
        this.cap = cap;
        cache = new LinkNode();
        map = new HashMap<Integer, Node>();
    }

    /**
     * 将结点提升为最近
     * @param key
     */
    private void makeRecently(Integer key){
        Node node = map.get(key);
        //删除
        cache.remove(node);
        //重新插入到尾部
        cache.addFromEnd(node);
    }


    /**
     * 添加最近使用的元素
     */
    private void addRecently(Integer key, Integer val){
        Node node = new Node(key, val);
        map.put(key, node);
        cache.addFromEnd(node);
    }

    /**
     * 删除最久未使用的元素
     */
    private void removeLeastRecently(){
        // 链表头部的第一个元素就是最久未使用的
        Node node = cache.removeFirst();
        // 同时别忘了从 map 中删除它的 key
        map.remove(node.key);
    }

    /**
     * 获取一个元素
     * @param key
     * @return
     */
    public int get(Integer key){
        if (!map.containsKey(key)){
            return -1;
        }else {
            Node node = map.get(key);
            makeRecently(key);
            return node.val;
        }
    }

    /**
     * 插入一个元素
     * @param key
     * @param val
     */
    public void put(Integer key, Integer val){
        //是否包含
        if (map.containsKey(key)){
            makeRecently(key);
            return;
        }
        if (map.size() >= cap){
            removeLeastRecently();
        }
        addRecently(key, val);
    }
}
